Tree structures can be used to store data in an ordered fashion. For instance, one kind of tree structure is a balanced tree or “b-tree.” B-trees comprise a number of nodes organized along a parent-child relationship. In general, parent nodes will store data (or pointers and/or links to data) having a particular value and link to a number of “children” nodes that also store data (or, again, links to data) having a particular value. At leaf level, the nodes will store data. Typically, a given parent node will have a “left” child that stores values less than the smallest value stored by the parent and a number of “right” children, each corresponding to a subset of values in parent, that store data having values greater than the greatest value in that particular subset in the parent. Consider, for instance, a simple b-tree having three nodes. If the parent node stores data with a value of 2, then the left child node might store data with a value of 1 and the right child node might store data with a value of 3. When a tree has both its left arm and right arm populated (and any associated sub-arms) the tree is said to be “balanced.”
Existing algorithms to build b-trees require comparing a data element (e.g., a key) to be inserted with the data elements that have already been inserted to find the correct position to insert the data element. Additionally, the b-tree needs to be balanced and/or rebalanced when any individual node gets over-filled. As part of this balancing, data elements stored in the various nodes must be moved to other nodes. All of these operations can incur both time and resource costs. It is, therefore, better to minimize these operations as much as possible.
In the drawings, like reference numbers generally indicate identical or similar elements. Additionally, generally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.